﻿// 0820train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
    TreeNode() = default;
    TreeNode(int val) :val(val) {};
};

TreeNode* BuildNode(vector<int>&tree_vec)
{
    queue<TreeNode*>bfs_queue;
    TreeNode* root = new TreeNode(tree_vec[0]);
    bfs_queue.push(root);

    int index = 1;
    while (!bfs_queue.empty() && index<tree_vec.size())
    {
        TreeNode* top_node = bfs_queue.front();
        bfs_queue.pop();

        if (index<tree_vec.size()&&tree_vec[index]!=INT_MIN)
        {
            top_node->left = new TreeNode(tree_vec[index]);
            bfs_queue.push(top_node->left);
        }
        index++;
        if (index < tree_vec.size() && tree_vec[index] != INT_MIN)
        {
            top_node->right = new TreeNode(tree_vec[index]);
            bfs_queue.push(top_node->right);
        }
        index++;
	    
    }
    return root;
}

/*
  1
2   3
 */
class Solution01 {
public:
    int getHeight(TreeNode* root)
    {
	    if (root==nullptr)
	    {
            return 0;
	    }
        return max(getHeight(root->left), getHeight(root->right)) + 1;
    }
    bool isBalanced(TreeNode* root) {
        if (root == nullptr) return true;

        return abs(getHeight(root->left) - getHeight(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
};

/*
 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 输出：[[5,4,11,2],[5,8,4,5]]
 */
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    vector<vector<int>>result_vec;
    if (root == nullptr) return result_vec;

    queue<TreeNode*>bfs_queue;
    queue<int>value_queue;
    queue<vector<int>>track_queue;
    

    bfs_queue.push(root);
    value_queue.push(root->val);
    vector<int>root_vec = { root->val };
    track_queue.push(root_vec);

    while (!bfs_queue.empty())
    {
        TreeNode* top_node = bfs_queue.front();
        bfs_queue.pop();
        int top_value = value_queue.front();
        value_queue.pop();
        vector<int>top_vec = track_queue.front();
        track_queue.pop();

        if (top_value==targetSum)
        {
            if (top_node->left==nullptr && top_node->right==nullptr)
            {
                result_vec.push_back(top_vec);
            }
            
        }
        
            if (top_node->left!=nullptr)
            {
                bfs_queue.push(top_node->left);
                int left_val = top_node->left->val;
                value_queue.push(top_value+left_val);

                vector<int>new_vec = top_vec;
                new_vec.push_back(left_val);
                track_queue.push(new_vec);
            }

            if (top_node->right!=nullptr)
            {
                bfs_queue.push(top_node->right);
                int right_val = top_node->right->val;
                value_queue.push(top_value + right_val);

                vector<int>new_vec = top_vec;
                new_vec.push_back(right_val);
                track_queue.push(new_vec);
            }

        
    }
    return result_vec;
}

/*
输入：root = [4,2,9,3,5,null,7]
输出：15
 */
class Solution02 {
public:
    int ans = 0;
    int dfs(TreeNode* node)
    {
        if (node == nullptr) return 0;
        int left_val = dfs(node->left);
        int right_val = dfs(node->right);

        ans += abs(right_val - left_val);
        return left_val + right_val + node->val;
    }
    int findTilt(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

int main()
{
    //root = [3,9,20,null,null,15,7]
    const int null = INT_MIN;
    vector<int>tree_vec = { 4,2,9,3,5,null,7 };
    TreeNode* root = BuildNode(tree_vec);
    //Solution01 solu;
    //cout << solu.isBalanced(root);
    //root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
    //int targetSum = 15;
    Solution02 solu;
    cout << solu.findTilt(root);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
